package com.zjsru.plan2024.oneday;

/**
 * 2717. 半有序排列
 *
 * @Author: cookLee
 * @Date: 2024-12-11
 */
public class SemiOrderedPermutation {

    /**
     * 主
     * \
     * 如果排列的第一个数字等于 1 且最后一个数字等于 n ，则称其为 半有序排列 。你可以执行多次下述操作，直到将 nums 变成一个 半有序排列 ：
     * \
     * 输入：nums = [2,1,4,3]
     * 输出：2
     * 解释：可以依次执行下述操作得到半有序排列：
     * 1 - 交换下标 0 和下标 1 对应元素。排列变为 [1,2,4,3] 。
     * 2 - 交换下标 2 和下标 3 对应元素。排列变为 [1,2,3,4] 。
     * 可以证明，要让 nums 成为半有序排列，不存在执行操作少于 2 次的方案。
     * \
     * 输入：nums = [2,4,1,3]
     * 输出：3
     * 解释：
     * 可以依次执行下述操作得到半有序排列：
     * 1 - 交换下标 1 和下标 2 对应元素。排列变为 [2,1,4,3] 。
     * 2 - 交换下标 0 和下标 1 对应元素。排列变为 [1,2,4,3] 。
     * 3 - 交换下标 2 和下标 3 对应元素。排列变为 [1,2,3,4] 。
     * 可以证明，要让 nums 成为半有序排列，不存在执行操作少于 3 次的方案。
     * \
     * 输入：nums = [1,3,4,2,5]
     * 输出：0
     * 解释：这个排列已经是一个半有序排列，无需执行任何操作。
     * \
     *
     * @param args args
     */
    public static void main(String[] args) {
        SemiOrderedPermutation semiOrderedPermutation = new SemiOrderedPermutation();
        int[] nums = new int[]{2, 1, 4, 3};
        System.out.println(semiOrderedPermutation.semiOrderedPermutation(nums));
    }

    public int semiOrderedPermutation(int[] nums) {
        int len = nums.length;
        int first = 0;
        int last = 0;
        for (int i = 0; i < len; i++) {
            if (nums[i] == 1) {
                first = i;
            } else if (nums[i] == len) {
                last = i;
            }
        }
        //如果first小于last，操作次数（first + （len - 1 - last ））
        return first < last ? first + (len - 1 - last) : first + (len - 1 - last) - 1;
    }

}
